package lz.secondinterview;

public class BinaryTree {

    /**
     * 生成n层的二叉树，递归调用
     * @param n
     */
    public Node createBinaryTree(int n) {
        Node<Integer> root = new Node();
        //root.setData(null);
        root.setData(1);
        createBinaryNode(root, n-1);
        return root;
    }

    private void createBinaryNode(Node<Integer> parent, int n) {
        if(n==0) {
            return;
        }
        Node<Integer> left = new Node();
        left.setData(parent.getData()*2);
        parent.setLeft(left);
        left.setParent(parent);
        Node<Integer> right = new Node();
        right.setData(parent.getData()*2+1);
        parent.setRight(right);
        right.setParent(parent);
        createBinaryNode(left, n-1);
        createBinaryNode(right, n-1);
    }

/*    public Node createBinaryTree(int n, int step) {
        Node<Integer> root = new Node();
        root.setData(1);
        createBinaryNode(root, n-1, step+1);
        return root;
    }

    private void createBinaryNode(Node<Integer> parent, int n) {
        if(n==0) {
            return;
        }
        Node<Integer> left = new Node();
        left.setData(step*2);
        parent.setLeft(left);
        left.setParent(parent);
        Node<Integer> right = new Node();
        right.setData(step*2+1);
        parent.setRight(right);
        right.setParent(parent);
        createBinaryNode(left, n-1, step+1);
        createBinaryNode(right, n-1, step+1);
    }*/

    public void traversePreOder(Node<Integer> root) {
        if(root == null) {
            return;
        }
        System.out.println(root.getData());
        traversePreOder(root.getLeft());
        traversePreOder(root.getRight());
        return ;
    }

    public Node<Integer> getRoot(Node<Integer> node) {
        Node<Integer> preNode = null;
        while(node.getParent() != null) {
            preNode = node;
            node = node.getParent();
            if(node.getLeft() == preNode) {
                System.out.println(node.getData());
                traversePreOder(node.getRight());
            } else {
                System.out.println(node.getData());
                traversePreOder(node.getLeft());
            }
        }
        return node;
    }

    public void traverseNode(Node<Integer> node)
    {
        traversePreOder(node);
        getRoot(node);
    }


    /**
     * 给二叉树赋值，
     *    1
     *  2   3
     * 4 5 6 7
     *
     * 遍历二叉树
     * 1. 不允许出现new关键字
     * 2. 不允许赋值
     * 3. 属性全为只读
     * 4. 遵循遍历规则只能访问一次。
     * @param args
     */
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Node<Integer> root = binaryTree.createBinaryTree(3);
        //Node<Integer> root = binaryTree.createBinaryTree(3, 0);
        binaryTree.traverseNode(root.getRight().getLeft());
        //binaryTree.getRoot(root);
        System.out.println();

    }
}

